Rbook-树状数组区间最值

# 区间最值

可以发现：对于\(x\)，可以直接转移到\(x\)的点只有，\(x-2^0\)，\(x-2^1\)，\(x-2^2\)，…，\(x-2^k\) (\(k\)满足\(2^k < lowbit(x)\)且\(2^{k+1}>=lowbit(x)\))

# 数学原理

若\(x = 1010000\)

\[ \begin{matrix} &=& 1001000 &+& lowbit(1001000) &=& 1001000 &+& 1000 &=& 1001000 &+& 2^3 \\ &=& 1001100 &+& lowbit(1001100) &=& 1001100 &+& 100 &=& 1001100 &+& 2^2 \\ &=& 1001110 &+& lowbit(1001110) &=& 1001110 &+& 10 &=& 1001110 &+& 2^1 \\ &=& 1001111 &+& lowbit(1001111) &=& 1001111 &+& 1 &=& 1001111 &+& 2^0\\ \end{matrix} \]

# 建立 / 尾插入

利用上面的性质,在树状数组的尾部插入数据,来建立一个树状数组

1
2
3
4
5
6
7
void push(int pos){
    int i,lb = lowbit(pos);
    c[pos] = a[pos];
    for(i=1;i<lb;i <<=1){
        c[pos] = max(c[pos],c[pos-i]);
    }
}

# update 维护树上的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* pos 位置,v 数值 */
void update(int pos,int v){
    int i,lb;
    c[pos] = a[pos] = v;
    lb = lowbit(pos);
    for(i=1;i<lb;i <<=1){ //利用孩子更新自己
        c[pos] = c[pos] > c[pos-i] ? c[pos] : c[pos-i];
    }
    int pre = c[pos];
    pos+=lowbit(pos);//父亲的位置

    /* 更新父亲 */
    while(pos <= n){
        if( c[pos] < pre){ //更新的父亲
            c[pos] = pre;
            pos +=lowbit(pos);
        }           //没有更新父亲
        else break;
    }
}

# query 查询区间最值

设\(query(x,y)\)求区间\([x,y]\)之间的最值, 已知\(c[x]\)表示\([x-lowbit(x)+1,x]\)之间的最值,那如何求区间\([x,y]\)的最值呢?

graph g {
    node[shape=rect width=1 style=filled fillcolor="lightblue"];

    1[pos="1,0!"];
    2[pos="2,0!"];
    3[pos="3,0!"];
    4[pos="4,0!"];
    5[pos="5,0!"];
    6[pos="6,0!"];
    7[pos="7,0!"];
    8[pos="8,0!"];

    node[shape=circle width=0.5 style=filled fillcolor="white"];
    c1[pos="1,0.55!" label="1"];
    c2[pos="2,1.55!" label="2"];
    c3[pos="3,0.55!" label="3"];
    c4[pos="4,2.55!" label="4"];
    c5[pos="5,0.55!" label="5"];
    c6[pos="6,1.55!" label="6"];
    c7[pos="7,0.55!" label="7"];
    c8[pos="8,3.55!" label="8"];
    c8--c4--c2--c1;
    c2--2;
    c4--{c3,4};
    c6--{c5,6};
    c8--{c6,c7,8};
}

想一想:

如果求区间\([1,8]\)的最值, 就需要点\(c[8]\)
如果求区间\([1,7]\)的最值, 就需要点\(c[7],c[6],c[4]\)
如果求区间\([2,7]\)的最值, 就需要点\(c[7],c[6],a[4],c[3],a[2]\)
如果求区间\([2,2]\)的最值, 就需要点\(a[2]\)
如果求区间\([2,8]\)的最值, 就需要点\(a[8],c[7],c[6],a[4],c[3],a[2]\)

所以,我们发现下面的规律, 因为\(y-lowbit(y)+1\)表示\(c[y]\)结点所管辖范围的最左边的点

若\(y-lowbit(y)+1 >=x\),则\(query(x,y) = max(c[y],query(x,y-lowbit(y)))\);
若\(y-lowbit(y)+1 <x\),则\(query(x,y) = max(a[y],query(x,y-1))\);
边界\(x > y\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//求区间[x,y]的最大值
int query(int x,int y){

    int res = -1;
    while(x <= y){
        int nx = y - lowbit(y)+1; //最左边的点
        if(nx >= x ){
            res = res < c[y] ? c[y] :res;
            y = nx-1; // 下一个求解区间
        }
        else { // nx < x
            res = res < a[y] ? a[y] :res;
            y--;
        }
    }
    return res;
}

# 总结

特点:

每一次在尾部添加一个数值,时间为\(log(n)\)
可以保留原数组的相对位置不变
如果不进行单点修改,速度更快

综上:

树状数组求区间最值特别适合那些:一边在尾部添加数据,一边查询最值的题目

# 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Bit_max {
    T a[maxn],c[maxn]; // a是原数组
    comp com;
    inline int lowbit(T x) { return x & -x;      }
    inline int fa(int p)   { return p+lowbit(p); }
    inline int left(int p) { return p-lowbit(p); }
    inline T g(T a ,T b) { return com(a,b) ? a : b;}
    void update_by_child(int p,T v){ //alias push
        c[p] = a[p] = v;
        int lb = lowbit(p);
        for(int i=1;i < lb ;i <<= 1)
            c[p] = g(c[p],c[p-i]);
    }

    void update(int p,T v){
        update_by_child(p, v);
        T t = c[p];
        for( p = fa(p); p<=N ; p = fa(p)){
            if( com(t,c[p]) ) c[p] = t;
            else break;
        }
    }

    T query(int l,int r){ // 求区间最值
        T ret = a[l];
        for( ; l <=r; ){
            int next = left(r)+1;
            if( next >= l ) ret = g(ret,c[r]) , r = next-1;
            else            ret = g(ret,a[r]) , r--;
        }
        return ret;
    }
};
Bit_max<ll> bit;

# 模板题目

# 练习题目

题目	地址
「2019冬令营提高组」全连	war3oj 10099

树状数组 区间最值

目录